/*
 * @lc app=leetcode.cn id=287 lang=cpp
 *
 * [287] 寻找重复数
 */

// @lc code=start
class Solution
{
 public:
  int findDuplicate(vector<int>& nums)
  {
    int n = nums.size() - 1;
    int l = 1, r = n;
    while (l < r)
    {
      int mid = l + r >> 1;

      // 因为此题只能使用O(1)空间，所以不能使用map统计个数
      // 因为要求不能更改原数组所以不能对数组进行排序
      // 二分的思想: 抽屉原理去理解
      // 元素的范围是 [1,n] 但是有n+1个数，n个抽屉去放
      //：统计nums中[1,mid]范围的数cnl，[mid+1,n]范围的数cnr
      //: 不会出现cnl cnr都小于各自区间的抽屉数目
      // cnl大于抽屉数，则二分了两个区间，模板1

      int cnt = 0;
      for (auto x : nums)
      {
        if (x >= 1 && x <= mid)
        {
          cnt++;
        }
      }
      if (cnt > mid)
        r = mid;  // mid就是左边的抽屉数目
      else
        l = mid + 1;
    }
    return l;
  }
};
// @lc code=end
